#include <iostream>
#include <vector>
using namespace std;

//class Solution {
//public:
//    int mySqrt(int x) {
//        int left = 0, right = x;
//        while (left < right)
//        {
//            int mid = left + (right - left + 1) / 2;
//            if (mid * mid > right) right = mid - 1;
//            else    left = mid;
//        }
//        return left;
//    }
//};
//
//int main()
//{
//    Solution().mySqrt(8);
//    return 0;
//}
//
//
//class Solution {
//public:
//    int mySqrt(int x) {
//        if (x < 1) return 0;
//        int left = 1, right = x;
//        while (left < right)
//        {
//            long long mid = left + (right - left + 1) / 2;
//            if (mid * mid > x) right = mid - 1;
//            else    left = mid;
//        }
//        return left;
//    }
//};


//class Solution {
//public:
//    int peakIndexInMountainArray(vector<int>& arr) {
//        int n = arr.size();
//        int left = 0, right = n - 1;
//        while (left < right)
//        {
//            int mid = left + (right - left + 1) / 2;
//            if (arr[mid] > arr[mid - 1])   left = mid;
//            else right = mid - 1;
//        }
//        return left;
//    }
//};


//class Solution {
//public:
//    int findPeakElement(vector<int>& nums) {
//        int left = 0, right = nums.size() - 1;
//        while (left < right)
//        {
//            int mid = left + (right - left + 1) / 2;
//            if (nums[mid] > nums[mid - 1]) left = mid;
//            else right = mid - 1;
//        }
//        return left;
//    }
//};

